package first.bishiti;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @ClassName ExpressionSum
 * @description: 考虑了 数字>9，()的情况，但未考虑{}[]，负数的情况
 * @author: 荣燊
 * @create: 2021-07-04 10:37
 **/
public class ExpressionSum {
    // 用ArrayList<String>保存后缀表达式
    static ArrayList<String> suffixList = new ArrayList<>();
    // 用栈保存操作符
    static Stack<String> opStack = new Stack<>();

    // 表达式求值
    public static void main(String[] args) {
        String test = "(7+5*4*3+6)";
        List<String> strings = expressionToList(test);
        System.out.println("字符串转化为list集合形式为："+strings);
        ArrayList<String> strings1 = function1(strings);
        System.out.println("中缀表达式转化为后缀表达式为："+strings1);
        int i = function2(strings1);
        System.out.println("结果是："+i);
    }

    // 中缀表达式转后缀表达式，使用到了栈和ArrayList
    /**
     *3.当读取到左括号"("时，直接压栈，当读取到运算符时，分两种情况讨论
     *   a.当运算符栈为空或者栈顶操作符的优先级小于当前运算符优先级时(如+和-的优先级低于 * 和 /)，直接入栈
     *   b.当运算符不为空时且栈顶操作符的优先级大于或等于当前运算符优先级时，循环执行出栈操作并加入list中，
     *     直到遇到优先级小于当前运算符的元素为止。循环执行完后再将当前运算符压栈。另外需要注意的是，只有遇到右括号时，左括号才出栈
     *4.当遇到右括号")"时，循环执行出栈操作并加入到list中，直到遇到左括号为止。并将左括号弹出，但不加入list中
     *5.表达式的值读取完后，将操作符栈中的所有元素弹出并加入到list中
     */
    public static ArrayList<String> function1(List<String> expressionList) {
        for (String item : expressionList) {
            if (isNumber(item)) { // 数字直接入队
                suffixList.add(item);
            } else if ("(".equals(item)) { // 左括号直接入栈
                opStack.push(item);
            } else if (isOperator(item)) { // 操作符得分两种情况考虑
                // 如果当前字符的优先级大于栈顶字符优先级，则入栈
                if (opStack.isEmpty() || "(".equals(opStack.peek()) || priority(item) > priority(opStack.peek())) {
                    opStack.push(item);
                } else {
                    // 否则将栈中元素出栈如队，直到遇到大于当前操作符或者遇到左括号时
                    while (!opStack.isEmpty() && !"(".equals(opStack.peek())) {
                        if (priority(item) <= priority(opStack.peek())) {
                            suffixList.add(opStack.pop());
                        } else {
                            break;
                        }
                    }
                    // 当前操作符压栈
                    opStack.push(item);
                }
            } else if (")".equals(item)) { // 右括号那么就出栈
                while (!opStack.isEmpty()) {
                    if ("(".equals(opStack.peek()))  {
                        opStack.pop();
                        break;
                    } else {
                        suffixList.add(opStack.pop());
                    }
                }
            } else {

            }
        }
        // 循环完毕
        while (!opStack.isEmpty()) {
            suffixList.add(opStack.pop());
        }

        return suffixList;
    }

    // 判断字符是否为操作符
    public static boolean isOperator(String op){
        return op.equals("+") || op.equals("-") || op.equals("*") || op.equals("/");
    }

    // 判断是否为数字
    public static boolean isNumber(String num){
        // \d表示数字,+表示至少一个
        return num.matches("\\d+");
    }

    //获取操作符的优先级
    public static int priority(String op){
        if (op.equals("*") || op.equals("/")) {
            return 1;
        } else if (op.equals("+") || op.equals("-")) {
            return 0;
        }
        return -1;
    }

    // 将表达式字符串形式转为list形式，数字是多位数情况也考虑到了
    private static List<String> expressionToList(String expression) {
        int index = 0;
        List<String> list = new ArrayList<>();
        do{
            char ch = expression.charAt(index);
            if(ch < 47 || ch > 58){
                //是操作符，直接添加至list中
                index ++ ;
                list.add(ch+"");
            } else if(ch >= 47 && ch <= 58){
                //是数字,判断多位数的情况
                String str = "";
                while (index < expression.length() && expression.charAt(index) >=47 && expression.charAt(index) <= 58){
                    str += expression.charAt(index);
                    index ++;
                }
                list.add(str);
            }
        } while (index < expression.length());
        return list;
    }

    // 后缀表达式计算结果,此时是一个后缀表达式
    public static int function2(ArrayList<String> expression) {
        // 后缀表达式的计算
        Stack<Integer> resultStack = new Stack<>();

        for (String s : expression) {
            if (isNumber(s)) { // 是数字
                resultStack.add(Integer.parseInt(s));
            } else { // 是操作符
                int num2 = resultStack.pop();
                int num1 = resultStack.pop();
                int res = 0;
                if (s.equals("+")) {
                    res = num1+num2;
                } else if (s.equals("-")){
                    res = num1 - num2;
                } else if (s.equals("*")){
                    res = num1 * num2;
                } else if (s.equals("/")){
                    res = num1 / num2;
                } else {
                    throw new RuntimeException("运算符错误！");
                }
                resultStack.push(res);
            }
        }
        return resultStack.pop();
    }
}
